/*
题目链接：https://leetcode.cn/problems/broken-board-dominoes/description/
	刘沛民	2024-12-3
*/

class Solution {
public:
    int domino(int n, int m, vector<vector<int>>& broken) {
        int vis[n*m + 1];
        int match[n*m + 2];
        memset(match,-1,sizeof match);
        int mx[4] = {0,0,-1,1};
        int my[4] = {1,-1,0,0};
        int g[n][m];
        for(int i = 0; i < n;i++){
            for(int j = 0; j < m;j++){
                g[i][j] = 1;
            } 
        }
        for(auto p:broken){
            g[p[0]][p[1]] = 0;
        }
        vector<vector<int>> e(n*m + 3);
        for(int i = 0; i < n;i++){
            for(int j = 0; j < m;j++){
                if(!g[i][j]) continue;
                for(int k = 0; k < 4;k++){
                    int nx = i+ mx[k];
                    int ny = j+my[k];
                    if(nx >= n || ny >= m || nx < 0 || ny < 0|| !g[nx][ny]) continue;
                    if((i + j)%2) e[i*m+j].push_back({nx*m+ny});
                }
            }
        } 
        function<bool(int)> dfs = [&](int u){
            for(auto v:e[u]){
                if(vis[v]) continue;
                vis[v] = 1;
                if(match[v]==-1 || dfs(match[v])){
                    match[v] = u;
                    return 1;
                }
            }
            return 0;
        };
        int ans = 0;
        for(int i = 0; i < n*m;i++){
            memset(vis,0,sizeof vis);
            if(match[i]==-1){
                if(dfs(i)) ans++;
            }
        }
        return ans;

    }
};